package advance.day03;

import java.util.HashMap;
import java.util.Stack;

/**
 * 描述：
 *      构建一个数组的maxTree
 *      一个数组的maxTree的定义：
 *      1）数组必须没有重复元素
 *      2）MaxTree是一棵二叉树，数组的每一个值对应一个二叉树节点
 *      3）包括MaxTree树在内且在其中的每一棵子树上，值最大的节点都是树的头
 *
 *      单调栈确定某个元素的左右两边的最近大于当前元素的两个元素作为父节点
 *
 * @author hl
 * @version 1.0
 * @date 2020/11/5 19:52
 */
public class MaxTree {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }
    public static Node getMaxTree(int[] arr){
        Node[] nArr = new Node[arr.length];
        for (int i = 0; i < arr.length; i++) {
            nArr[i] = new Node(arr[i]);
        }
        Stack<Node> stack = new Stack<>();//单调栈
        HashMap<Node,Node> lBigMap = new HashMap<>();
        HashMap<Node,Node> rBigMap = new HashMap<>();
        for (int i = 0; i < nArr.length; i++) {
            Node curNode = nArr[i];
            while(!stack.isEmpty() && stack.peek().value < curNode.value){
                Node node = popSetMap(stack, lBigMap);//设置左边的最近的最大值
                rBigMap.put(node,curNode);//设置弹出结点的右边的最近的最大值
            }
            stack.add(curNode);
        }
        while(!stack.isEmpty()){
            popSetMap(stack, lBigMap);
        }
        Node head = null;//头节点
        for (int i = 0; i < nArr.length; i++) {
            Node curNode = nArr[i];
            Node left = lBigMap.get(curNode);
            Node right = rBigMap.get(curNode);
            if (left == null && right == null) {
                head = curNode;
            }else if (left == null) {
                if(right.left == null){//从左到右挂
                    right.left = curNode;
                }else{
                    right.right = curNode;
                }
            }else if (right == null) {
                if (left.left == null) {
                    left.left = curNode;
                }else{
                    left.right = curNode;
                }
            }else{
                Node parent = left.value < right.value ? left : right;
                if(parent.left == null){
                    parent.left = curNode;
                }else{
                    parent.right = curNode;
                }
            }
        }

        return head;
    }
    public static Node popSetMap(Stack<Node> stack, HashMap<Node,Node> map){
        Node curNode = stack.pop();
        if (stack.isEmpty()) {
//            map.put(curNode, null);
        }else{
            map.put(curNode,stack.peek());
        }
        return curNode;
    }
    //二叉树的先序遍历
    public static void printPreOrder(Node head) {
        if (head == null) { return; }
        System.out.print(head.value + " ");
        printPreOrder(head.left);  //递归调用遍历二叉树
        printPreOrder(head.right);
    }

    //二叉树的中序遍历
    public static void printInOrder(Node head) {
        if (head == null) { return; }
        printInOrder(head.left);
        System.out.print(head.value + " ");
        printInOrder(head.right);
    }
    public static void main(String[] args) {
        int[] arr = {3, 4, 5, 1, 2};
        Node head = getMaxTree(arr);
//        printPreOrder(head);
//        System.out.println();
//        printInOrder(head);
        printTree(head);
    }
    public static void printTree(Node head) {
        System.out.println("Binary Tree:");
        printInOrder(head, 0, "H", 17);
        System.out.println();
    }

    public static void printInOrder(Node head, int height, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.right, height + 1, "v", len);
        String val = to + head.value + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.left, height + 1, "^", len);
    }

    public static String getSpace(int num) {
        String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }
}
